#include "BTreeNode.h"
#include <iostream>

using namespace std;


BTLeafNode::BTLeafNode()
{
    memset(&buffer, 0, sizeof(buffer));
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
    RC rc;
    if ((rc  = pf.read(pid, (char*)&buffer)) < 0) return rc;
    return 0;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{ 
    RC rc;
    if ((rc = pf.write(pid, (char*)&buffer)) < 0) return rc;
    return 0; 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
    return buffer.num_entries;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
    if (buffer.num_entries >= MAX_ENTRIES)
       return RC_NODE_FULL; 
    int i = buffer.num_entries;
    while (i > 0 && buffer.entries[i-1].key > key)
    {
        buffer.entries[i].key = buffer.entries[i-1].key;
        buffer.entries[i].rid = buffer.entries[i-1].rid;
        i--;
    }
    buffer.entries[i].key = key;
    buffer.entries[i].rid = rid;
    buffer.num_entries++;
    return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{ 
    RC rc;
    if ((rc = insert(key, rid)) < 0) return rc;
    int half_entries = buffer.num_entries / 2;
    siblingKey = buffer.entries[half_entries].key;
    for (int i = half_entries; i < buffer.num_entries; i++)
        sibling.insert(buffer.entries[i].key, buffer.entries[i].rid);
    buffer.num_entries = half_entries;
    return 0; 
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
    int i = 0;
    while (i < buffer.num_entries && searchKey > buffer.entries[i].key)
        i++;
    if (i == buffer.num_entries)
        return RC_NO_SUCH_RECORD;
    eid = i;
    return 0;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{
    if (eid >= buffer.num_entries)
        return RC_NO_SUCH_RECORD;
    key = buffer.entries[eid].key;
    rid = buffer.entries[eid].rid;
    return 0;
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{
    return buffer.pid;
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{
   buffer.pid = pid; 
   return 0;
}



//**********
// NON-LEAF
//**********

BTNonLeafNode::BTNonLeafNode()
{
    memset(&buffer, 0, sizeof(buffer));
}


/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
    RC rc;
    if ((rc  = pf.read(pid, (char*)&buffer)) < 0) return rc;
    return 0;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{
    RC rc;
    if ((rc = pf.write(pid, (char*)&buffer)) < 0) return rc;
    return 0;
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
    return buffer.num_entries;
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ if (buffer.num_entries >= 126)
    return RC_NODE_FULL;
    int i = buffer.num_entries;

    while (i > 0 && buffer.entries[i-1].key > key)
    {
        buffer.entries[i].key = buffer.entries[i-1].key;
        buffer.entries[i].pid = buffer.entries[i-1].pid;
        i--;
    }
    buffer.entries[i].key = key;
    buffer.entries[i].pid = pid;
    buffer.num_entries++;
    return 0;
}


/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
    RC rc;
    if ((rc = insert(key, pid)) < 0) return rc;
    int half_entries = buffer.num_entries / 2;
    midKey = buffer.entries[half_entries].key;
    for (int i = half_entries+1; i < buffer.num_entries; i++)
        sibling.insert(buffer.entries[i].key, buffer.entries[i].pid);
    buffer.num_entries = half_entries;
    return 0; 
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
    int i = 0;
    while (i < buffer.num_entries && searchKey >= buffer.entries[i].key)
        i++;
    
    if (i > buffer.num_entries)
        return RC_NO_SUCH_RECORD;
    
    if (i == 0) pid = buffer.firstPid;
    else pid =buffer.entries[i-1].pid;
    return 0; 
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
    buffer.firstPid = pid1;
    NonLeafNodeEntry rootNode;
    rootNode.key = key;
    rootNode.pid = pid2;
    buffer.num_entries = 1;
    buffer.entries[0] =rootNode;
    return 0;
}

